\extitle{4}{二次互反律}

\section{二 次剩 余}


\begin{exercise}\label{1的平方根个数之模素数的幂}
记 $x^{2} \equiv 1 \left(\mod m\right)$ 的解的个数为 $N$ (解数按模 $m$ 陪集计). 证明：
若 $m=p^{s}$, $p$ 为奇素数，则 $N=2, x\equiv \pm 1$; 
若 $m=2$ 或 $4$, 则 $N=1$ 或 $2$; 
若 $m=2^{s} \geqslant 8$, 则 $N=4, x\equiv \pm 1$ 或 $2^{s-1} \pm 1$.
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item $m=p^{s}$, $p$ 为奇素数。显然$x\equiv \pm 1\left( \mod p^s \right)$为$x^2\equiv 1\left( \mod p^s \right)$的两个解。只用说明这是所有解即可，或者说，$x^2\equiv 1\left( \mod p^s \right)$只有两个解。
      由于$\FF_p$为域，$x^2\equiv 1\left( \mod p \right)$至多两个解，故$x\equiv \pm 1\left( \mod p \right)$为全部解。
      因此$x^2\equiv 1\left( \mod p \right)$恰有两个解。由\S3.5定理2知$x^2\equiv 1\left( \mod p^s \right)$恰有两个解。
    \item $m=2$时 $x^{2} \equiv 1 \left(\mod m\right)$有唯一解$x\equiv 1\left( \mod m \right)$;  
      $m=4$时$x^{2} \equiv 1 \left(\mod m\right)$有两解$x\equiv \pm 1\left( \mod m \right)$.
    \item $m=2^s$, $s\geqslant 3$. 用\S3.5定理1的记号。$d_0=2$, $d=(2,2^{s-2})=2$. 故由\S3.5定理1知解数$N=d_0d=4$.
      容易直接验证$x\equiv \pm 1$ 或 $2^{s-1} \pm 1$是$x^{2} \equiv 1 \left(\mod 2^s\right)$的$4$个不同解，故是全部解。

      亦可如\S3.5定理1的证明中算出所有解。
      令$x\left( \mod 2^s \right)$的指标为$(\varepsilon, y)$, 即
      $x\equiv (-1)^{\varepsilon}5^y\left( \mod 2^s \right)$. 
      显然$1\left( \mod 2^s \right)$的指标为$(0,0)$.
      $x^2\equiv 1\left( \mod 2^s \right)$相当于
      \[
        2\varepsilon\equiv 0\left( \mod 2 \right), \quad 2y\equiv 0\left( \mod 2^{s-2} \right).
      \]
      因此$\varepsilon=0,1$, $y=0, 2^{s-3}$. 
      由\S3.3的证明知$5^{2^{s-3}}\equiv 2^{s-1}+1\left( \mod 2^s \right)$. 
      进而可知
$x^{2} \equiv 1 \left(\mod 2^s\right)$的所有解为
\begin{align*}
  (-1)^05^{0}&\equiv 1, &
  (-1)^05^{2^{s-3}}&\equiv 2^{s-1}+1,\\
  (-1)^1 5^{0}&\equiv -1, &
  (-1)^1 5^{2^{s-3}}&\equiv 2^{s-1}-1.
  \tag*{\qedhere}
\end{align*}
  \end{enumerate}
\end{solution}

\begin{exercise}\label{1的平方根个数之模m}
  设 $m=2^{s} p_{1}^{s_{1}} \cdots p_{\omega}^{s_{\omega}}, m_{i}=p_{i}^{s}$ (记 $s=s_{0}, 2=p_{0}$ ). 证明： $N=N_{0} \cdots N_{\omega}$, 其中 $N$ 为 $x^{2} \equiv 1$ $ \left(\mod m\right)$ 的解个数， $N_{i}$ 为 $x^{2} \equiv 1\left(\mod m_{i}\right)$ 的解个数。
\end{exercise}

\begin{solution}
  由\S3.5定理1立知。
\end{solution}

\begin{exercise}\label{1的平方根个数计数}
如上题设 $m=2^{s} p_{1}^{s_{1}} \cdots p_{\omega}^{s_\omega}, N$ 为 $x^{2} \equiv 1 \left(\mod m\right)$ 解个数。 证明：当 $s=0,1,2, \geqslant 3$ 时，
分别有 $N=2^{\omega}, 2^{\omega}, 2^{\omega+1}, 2^{\omega+2}$.
\end{exercise}

\begin{solution}
  由练习~\ref{1的平方根个数之模素数的幂}~和~\ref{1的平方根个数之模m}~立知。
\end{solution}

\begin{exercise}
  设 $m$ 和符号如上题。 证明： 若 $x^{2} \equiv a \left(\mod m\right)$ 有解且$(a,m)=1$, 则解数 $N_{a}=N$.
\end{exercise}

\begin{solution}
  令$x_0$为$a\left( \mod m \right)$的一个平方根。
  $(a,m)=1$表明$(x_0, m)=1$. 
$x^{2} \equiv a \left(\mod m\right)$等价于
$x^2\equiv x_0^2\left( \mod m \right)$, 亦等价于
$(x_0^{-1}x)^2\equiv 1\left( \mod m \right)$. 
由练习~\ref{1的平方根个数计数}~知其解数为$N$.
\end{solution}

\begin{exercise}
  证明： $a$ 为模 $p^{s}$ 的二次非剩余 (奇素数 $p \nmid a$) 当且仅当 $a^{\frac{p-1}{2}} \equiv-1 \left(\mod p\right)$.
\end{exercise}

\begin{solution}
  这是引理1(2).
\end{solution}

\begin{exercise}
\begin{enumerate}
  \item 用Euler判别法决定 $\kronecker{2}{5},\kronecker{3}{7},\kronecker{5}{13}$.
  \item 用 Gauss 引理决定 $\kronecker{5}{7},\kronecker{3}{11},\kronecker{-1}{p}$.
\end{enumerate}
\end{exercise}

\begin{solution}
\begin{enumerate}
  \item 
    Euler判别法要求我们计算$a^{\frac{p-1}{2}}\left( \mod p \right)$来确定Legendre符号$\kronecker{a}{p}$.
    \begin{enumerate}
      \item 计算$\kronecker{2}{5}$. 有$\kronecker{2}{5}\equiv 2^{2} \equiv -1\left( \mod 5 \right)$. 故$\kronecker{2}{5}=-1$.
      \item 计算$\kronecker{3}{7}.$ 有$\kronecker{3}{7}\equiv 3^{3} \equiv -1\left( \mod 7 \right)$. 故$\kronecker{3}{7}=-1$.
      \item 计算$\kronecker{5}{13}.$ 有$\kronecker{5}{13}\equiv 5^{6}\equiv (-1)^3 \equiv -1\left( \mod 13 \right)$. 故$\kronecker{5}{13}=-1$.
    \end{enumerate}
  \item Gauss引理要求我们求出$\{a, 2a, \cdots, \frac{p-1}{2}a\}$的模$p$最小正剩余中大于$\frac{p}{2}$的个数来确定Legendre符号$\kronecker{a}{p}$.
    \begin{enumerate}
        %\item 计算$\kronecker{2}{5}$. $\frac{p-1}{2}=2$. $\{2, 2\cdot 2\}$的绝对最小剩余为$\{2,-1\}$, 其中负数个数为$\nu=1$. 故$\kronecker{2}{5}=-1$.
         % \item 计算$\kronecker{3}{7}$. $\frac{p-1}{2}=3$. $\{3, 2\cdot 3, 3\cdot 3\}$的绝对最小剩余为$\{3,-1,2\}$, 其中负数个数为$\nu=1$. 故$\kronecker{3}{7}=-1$.
            \item 计算$\kronecker{5}{7}$. $\frac{p-1}{2}=3$. $\{5, 2\cdot 5, 3\cdot 5\}$的最小正剩余为$\{5,3,1\}$, 其中大于$7/2$的个数为$\nu=1$. 故$\kronecker{5}{7}=-1$.
              \item 计算$\kronecker{3}{11}$. $\frac{p-1}{2}=5$. $\{3, 2\cdot 3, 3\cdot 3, 4\cdot 3, 5\cdot 3\}$的最小正剩余为$\{3,6,9,1,4\}$, 其中大于$11/2$的个数为$\nu=2$. 故$\kronecker{3}{11}=1$.
          %      \item 计算$\kronecker{5}{13}$. $\frac{p-1}{2}=6$. $\{5, 2\cdot 5, 3\cdot 5, 4\cdot 5, 5\cdot 5, 6\cdot 5\}$的绝对最小剩余为$\{5,-3,2,-6,-1,4\}$, 其中负数个数为$\nu=3$. 故$\kronecker{5}{13}=-1$.
              \item 计算$\kronecker{-1}{p}$. $\{-1, -2, \cdots, -\frac{p-1}{2}\}$的最小正剩余$\{p-1,p-2,\cdots,\frac{p+1}{2}\}$, 其中大于$\frac{p}{2}$的个数为$\nu=\frac{p-1}{2}$. 故$\kronecker{-1}{p}=(-1)^{\frac{p-1}{2}}$.
                      \qedhere
                    \end{enumerate}
                \end{enumerate}
\end{solution}

\begin{exercise}\label{用legendre符号表示解数}
  证明： $x^{2} \equiv a \left(\mod p\right)$ 的解数为 $1+\kronecker{a }{ p}$.
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item 若$p\mid a$, 则$\kronecker{a}{p}=0$, 且$x^{2} \equiv a \left(\mod p\right)$有唯一解$x\equiv 0\left( \mod p \right)$.
    \item 若$a$为模$p$二次剩余，则$\kronecker{a}{p}=1$, 且$x^{2} \equiv a \left(\mod p\right)$有两个解。这里注意到：若$x_0$为一解，则$-x_0$亦为解; 由于$p$为奇素数，$(x_0, p)=1$ (因为$(a,p)=1$), 有$x_0\nequiv -x_0\left( \mod p \right)$; 而$x^2-a\in \FF_p[x]$至多两个解，因此$\pm x_0$为全部解。
    \item 若$a$为模$p$二次非剩余，则$\kronecker{a}{p}=-1$, 且$x^{2} \equiv a \left(\mod p\right)$没有解。
   \end{enumerate}
  综上可知，在任何情况下，总有
  解数$N=1+\kronecker{a }{ p}$.
\end{solution}

\begin{exercise}
  设 $p \nmid a$, 证明： $a x^{2}+b x+c \equiv 0 \left(\mod p\right)$ 的解数为 $1+\kronecker{b^{2}-4 a c}{ p}$.
\end{exercise}

\begin{solution}
  注意到$2a\left( \mod p \right)$可逆。
易知$a x^{2}+b x+c \equiv 0 \left(\mod p\right)$相当于
\[
  \left( 2ax+b \right)^2 \equiv b^2-4ac\left( \mod p \right).
\]
显然此方程的解集与同余方程$y^2\equiv b^2-4ac\left( \mod p \right)$的解集一一对应。
从而由练习~\ref{用legendre符号表示解数}~知解数为
\[\tag*{\qedhere}
1+\kronecker{b^{2}-4 a c}{ p}.
\]
\end{solution}

\begin{exercise}
  证明： $x^{2}-y^{2} \equiv a \left(\mod p\right)$ 的解数为 $\sum_{y=0}^{p-1} 1+\kronecker{y^{2}+a}{ p}$.
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
直接计算证实 $x^{2}-y^{2} \equiv a \left(\mod p\right)$ 的解数为 $2 p-1$ 或 $p-1$ (依 $p \mid a$ 或否).
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}\label{求a的平方根}
  证明：若$a$为素数$p$的二次剩余，则$x^2\equiv a\left( \mod p \right)$的解为
  \begin{enumerate}
    \item $x\equiv \pm a^{n+1}\left( \mod p \right)$, 若$p=4n+3$;
    \item $x\equiv \pm a^{n+1}$ 或 $\pm 2^{2n+1} a^{n+1}\left( \mod p \right)$, 若$p=8n+5$.
  \end{enumerate}
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item 由 $\kronecker{a }{ p}=1$ 知 $a^{2n+1}=a^{\frac{p-1}{2}} \equiv 1\left(\mod  p\right)$, 故
\[
  \begin{aligned}
    a^{2n+2} \equiv a \quad\left(\mod  p\right), \quad\text{从而}\quad
  \left(a^{n+1}\right)^{2} \equiv a \quad\left(\mod  p\right).
\end{aligned}
\]
故同余式 $x^{2} \equiv a\left(\mod  p\right)$ 的解为$x \equiv \pm a^{n+1}$.
\item 由 $a^{4n+2}=a^{\frac{p-1}{2}} \equiv \kronecker{a}{p}= 1\left(\mod  p\right)$ 可得
\[
\begin{aligned}
  a^{2n+1} \equiv \pm 1 \left(\mod  p\right),\quad \text{从而}\quad
  (a^{n+1})^{2} = a^{2n+2} \equiv \pm a \left(\mod  p\right).
\end{aligned}
\]
正号情形已得解，两个解为$x\equiv \pm a^{n+1}\left( \mod p \right)$.
在负号情形，注意到$-1$有平方根$2^{2n+1}$.
诚然，我们有%
\footnote{对任一个非二次剩余$b$都有$b^{2n+1}$是$-1$的平方根。
另外，由于$p\equiv 1\left( \mod 4 \right)$, \S4.1引理2(2)表明$(\frac{p-1}{2})!$是$-1$的平方根。
当然，$-1\left( \mod p \right)$的平方根至多两个，这些无非相差个符号。}
  \[
  -1\equiv \kronecker{2}{p} \equiv 2^{\frac{p-1}{2}}\equiv 2^{4n+2}=(2^{2n+1})^2 \left( \mod p \right).
\]
从而
\[
  (2^{2n+1} a^{n+1}  )^{2} \equiv a \quad\left(\mod  p\right),
\]
也可得 $x^{2} \equiv a\left(\mod  p\right)$的两个解为
\[\tag*{\qedhere}
  x\equiv \pm 2^{2n+1} a^{n+1} \left( \mod p \right).
\]
  \end{enumerate}
\end{solution}


\begin{exercise}
  证明：若$p$是素数且$p=8n+1$, $g$为模$p$原根，则
  $x^2\equiv \pm 2\left( \mod p \right)$的解为
  \[
    x\equiv \pm (g^{7n}\pm g^n)\left( \mod p \right),
  \]
  其中括号里外的 $\pm$ 同时取正或负。
\end{exercise}

\begin{exercise}
  求解同余方程$x^2\equiv 207\left( \mod 1001 \right)$.
\end{exercise}

\begin{exercise}
  证明：若整数$b$不被奇素数$p$整除，则
  \[
    \kronecker{b}{p} + \kronecker{2b}{p} + \cdots + \kronecker{(p-1)b}{p} = 0.
  \]
\end{exercise}

\begin{proof}
  注意到$b,2b,\cdots,(p-1)b$互不同余，故
  \[
    \{b,2b,\cdots,(p-1)b\}\equiv \{1,2,\cdots,p-1\}\left( \mod p \right).
  \]
  由系1(3)知其中一半为二次剩余，一半为二次非剩余。故
  \[\tag*{\qedhere}
    \kronecker{b}{p} + \kronecker{2b}{p} + \cdots + \kronecker{(p-1)b}{p} = 0.
  \]
\end{proof}

\section{二次互反律}



\begin{exercise}\label{6是模p的二次剩余的条件}
求所有的素数 $p$, 使得 $6$ 是模 $p$ 的二次剩余。
\end{exercise}

\begin{solution}
  $1=\kronecker{6}{p}=\kronecker{2}{p}\kronecker{3}{p}$相当于
  $\kronecker{2}{p}=1=\kronecker{3}{p}$, 或$\kronecker{2}{p}=-1=\kronecker{3}{p}$.
  由\S4.1引理4和\S4.2例1分别知
  \[
  \begin{aligned}
  \kronecker{2}{p}&= (-1)^{\frac{ p^{2}-1}{ 8}}=
\begin{cases}
1, & \text { 若~} p \equiv \pm 1 \left(\mod  8\right) \\
-1, & \text { 若~} p \equiv \pm 3 \left(\mod  8\right),
\end{cases} \\
\kronecker{3 }{ p}&= \begin{cases}
1 & \text{若~} p \equiv \pm 1 \left(\mod  12\right) \\
-1 & \text{若~} p \equiv \pm 5 \left(\mod  12\right).
\end{cases}
\end{aligned}
\]
因此，
\begin{enumerate}
\item 
$\kronecker{2}{p}=1=\kronecker{3}{p}$当且仅当$p \equiv \pm 1 \left(\mod  8\right)$且$p \equiv \pm 1 \left(\mod  12\right)$, 亦即$p \equiv \pm 1 \left(\mod  24\right)$. 这里注意到：模$4$可知，$p \equiv 1 \left(\mod  8\right)$且$p \equiv - 1 \left(\mod  12\right)$不可能，$p \equiv -1 \left(\mod  8\right)$且$p \equiv 1 \left(\mod  12\right)$不可能）。
\item $\kronecker{2}{p}=-1=\kronecker{3}{p}$当且仅当$p \equiv \pm 3 \left(\mod  8\right)$且$p \equiv \pm 5 \left(\mod  12\right)$, 亦即$p \equiv \pm 5 \left(\mod  24\right)$. 这里注意到：模$4$可知，$p \equiv 3 \left(\mod  8\right)$且$p \equiv 5\left(\mod  12\right)$不可能，$p \equiv -3 \left(\mod  8\right)$且$p \equiv -5 \left(\mod  12\right)$不可能。另外，要求解$p \equiv 3 \left(\mod  8\right)$且$p \equiv -5\left(\mod  12\right)$, 或 $p \equiv -3 \left(\mod  8\right)$且$p \equiv 5\left(\mod  12\right)$, 参见\S2.5, 练习6.
\end{enumerate}
综上可知，$6$ 是模 $p$ 的二次剩余当且仅当$p\equiv \pm1,\pm5\left( \mod 24 \right)$.
\end{solution}

\begin{exercise}
用二次互反律， 求 $a=7$ 是模 $p$ 二次剩余的所有奇素数 $p$. 对 $a=15$ 同样做。
\end{exercise}

\begin{solution}
\begin{enumerate}
  \item 令$q=7$. 我们应用定理2(2). 注意到模 $4q =28$ 与$q=7$互素的奇数为$\pm 1, \pm3, \pm 5, \pm9, \pm11, \pm13$.
故模 $4 q=28$ 的 $p \equiv \pm b^{2}$ 只可能为 $\pm 1, \pm 9, \pm 25, \mp 3, \pm 9, \pm1$. 
       由定理 2(2),  $7$是模 $p$ 二次剩余当且仅当$p\equiv \pm1, \pm 3, \pm9\left( \mod 28 \right)$.
  \item 令$a=15$. $\kronecker{a}{p}=1$相当于
$\kronecker{3}{p}=1=\kronecker{5}{p}$, 或$\kronecker{3}{p}=-1=\kronecker{5}{p}$.
由\S4.2例1和\S4.2例2分别知
   \[
     \begin{aligned}   
\kronecker{3 }{ p}&= \begin{cases}
1 & \text{若~} p \equiv \pm 1 \left(\mod  12\right) \\
-1 & \text{若~} p \equiv \pm 5 \left(\mod  12\right),
\end{cases}\\
\kronecker{5}{ p}&= \begin{cases}
 1 & \text{若~} p \equiv \pm 1 \left(\mod  5\right) \\
   -1 & \text{若~} p \equiv \pm 3 \left(\mod 5\right).
   \end{cases}
 \end{aligned}
 \]
因此，
\begin{enumerate}
\item 
  $\kronecker{3}{p}=1=\kronecker{5}{p}$当且仅当$p \equiv \pm 1 \left(\mod  12 \right)$且$p \equiv \pm 1 \left(\mod  5\right)$, 亦即$p \equiv \pm 1, \pm 11 \left(\mod  60 \right)$ (用孙子定理, \S2.5定理1). 
\item $\kronecker{3}{p}=-1=\kronecker{5}{p}$当且仅当$p \equiv \pm 5 \left(\mod  12\right)$且$p \equiv \pm 3 \left(\mod  5\right)$, 亦即$p \equiv \pm 7,\pm 17 \left(\mod  60 \right)$ (用孙子定理, \S2.5定理1). 
\end{enumerate}
综上可知，$15$ 是模 $p$ 的二次剩余当且仅当$p\equiv \pm1,\pm7, \pm11, \pm17\left( \mod 60 \right)$.
\qedhere
\end{enumerate}
\end{solution}

\begin{exercise}
用 Jacobi 符号决定 $(7 / 15),(15 / 77),(113 / 997),(215 / 761),(514 / 1093)$, $(401 / 757)$.
\end{exercise}

\begin{solution} 
  我们应用Jacobi符号的性质。特别地，定理3表明：
  若$a, b$为正奇数，
  \begin{enumerate}[(i)]
    \item  $\kronecker{a}{b}=\kronecker{b}{a}$当且仅当$a$或$b$形如$4k+1$;
    \item $\kronecker{-1}{b}=1$当且仅当$b$形如$4k+1$;
    \item  $\kronecker{2}{b}=1$当且仅当$b$形如$8k\pm 1$.
\end{enumerate}
可知
  \begin{enumerate}
    \item $\kronecker{7}{15}= -\kronecker{15}{7} = -\kronecker{1}{7}=-1$.
    \item $\kronecker{15}{77}= \kronecker{77}{15}= \kronecker{2}{15}=1$.
    \item 我们有
    \[
    \begin{aligned}
          \kronecker{113}{997}&= \kronecker{997}{113}=\kronecker{93}{113}=\kronecker{113}{93}=\kronecker{20}{93}
              = \kronecker{4}{93}\kronecker{5}{93}=\kronecker{5}{93}\\
                  &= \kronecker{93}{5} = \kronecker{3}{5}=\kronecker{5}{3}=\kronecker{2}{3}=-1.
                \end{aligned}
  \]
  \item 我们有
\[
\begin{aligned}
      \kronecker{215}{761} &= \kronecker{761}{215} = \kronecker{116}{215}  = \kronecker{2^2\cdot 29}{215}=\kronecker{29}{215} 
          = \kronecker{215}{29}= \kronecker{12}{29}\\
          &= \kronecker{3}{29}=\kronecker{29}{3}=\kronecker{2}{3}=-1.
            \end{aligned}
\]
\item 我们有
\[
  \begin{aligned}
        \kronecker{514}{1093}&= \kronecker{2}{1093}\kronecker{257}{1093} = -\kronecker{1093}{257} = -\kronecker{65}{257} \\
        &= -\kronecker{257}{65} = -\kronecker{-3}{65} = -\kronecker{-1}{65}\kronecker{3}{65}=-\kronecker{65}{3}=-\kronecker{2}{3}=1.
          \end{aligned}
        \]
\item 我们有
\begin{align*}
      \kronecker{401}{757}&= \kronecker{757}{401}= \kronecker{356}{401} = \kronecker{2^2}{401}\kronecker{89}{401} 
          =\kronecker{401}{89} \\
          &=  \kronecker{45}{89} = \kronecker{89}{45} = \kronecker{-1}{45} = 1.
          \tag*{\qedhere}
        \end{align*}
\end{enumerate}
\end{solution}

\begin{exercise}
证明：若 $p=8 k-1$ 为素数， 则 $2^{4 k-1} \equiv 1 \left(\mod p\right)$. 由此可知
\[
  23\mid 2^{11}-1, \quad 71\mid  2^{35}-1, \quad 311 \mid 2^{155}-1.
\]
\end{exercise}

\begin{solution}
  既然$p=8 k-1$,
  由$\kronecker{2}{p}=(-1)^{\frac{p^2-1}{8}}$知
  $\kronecker{2}{p}=1$.
  由Euler判别法知
  \[
    \tag*{\qedhere}
    2^{4k-1}=2^{\frac{p-1}{2}}\equiv 1\left( \mod p \right).
  \]
\end{solution}


\begin{exercise}\label{求a的平方根(1)举例}
求解各同余式： $x^{2} \equiv 7 \left(\mod 43\right), x^{2} \equiv 11 \left(\mod 43\right), x^{2} \equiv 15 \left(\mod 163\right)$.
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item 
  求解$x^2\equiv 7\left( \mod 43 \right)$. 可算得$(7/43)=-1$. 故$x^2\equiv 7\left( \mod 43 \right)$无解。
\item   求解$x^2\equiv 11\left( \mod 43 \right)$. $43=4\times 10+3$. 可算得$(11/43)=1$. 进而由\S4.1 练习~\ref{求a的平方根}~知所给同余式有两个解为
\[
  x\equiv \pm 11^{10+1} \equiv \pm 21\left( \mod 43 \right).
\]
  \item   求解$x^2\equiv 15\left( \mod 163 \right)$. $163=4\times 40+3$. 可算得$(15/163)=1$. 进而由\S4.1 练习~\ref{求a的平方根}~知所给同余式有两个解为
    \[\tag*{\qedhere}
  x\equiv \pm 15^{40+1} \equiv \pm 34\left( \mod 163 \right).
\]
  \end{enumerate}
\end{solution}

\begin{exercise}\label{求a的平方根(2)举例}
求解各同余式： $x^{2} \equiv 7 \left(\mod 37\right), x^{2} \equiv 13 \left(\mod 101\right)$.
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item 求解$x^2\equiv 7\left( \mod 37 \right)$. 可计算得$(7/37)=1$, 
      故$7^{18}\equiv 1\left( \mod 37 \right)$. 又计算得$7^{9}\equiv 1\left( \mod 37 \right)$, 故
      \[
        (7^5)^2=7^{10}\equiv 7\left( \mod 37 \right).
      \]
  故由\S4.1 练习~\ref{求a的平方根}~知$x^2\equiv 7\left( \mod 37 \right)$的两个解为
  $x\equiv \pm 7^5\equiv \pm 9\left( \mod 37 \right)$.
\item 求解$x^2\equiv 13\left( \mod 101 \right)$. 可计算得$(13/101)=1$, 
  故$13^{50}\equiv 1\left( \mod 101 \right)$. 又计算得$13^{25} \equiv -1\left( \mod 101 \right)$, 故 $(13^{13})^2\equiv -13\left( \mod 101 \right)$.
  注意到$-1\equiv 100\left( \mod 101 \right)$的一个平方根为$10$, 
  有
  \[
    ( 13^{13} \cdot 10)^2 = (13^{13} \cdot 10)^2\equiv 13\left( \mod 101 \right).
    \]
  故由\S4.1 练习~\ref{求a的平方根}~知$x^2\equiv 13 \left( \mod 101 \right)$的两个解为
  \[\tag*{\qedhere}
    x\equiv \pm 13^{13}\cdot 10\equiv \pm 66\left( \mod 101 \right).
  \]
  \end{enumerate}
\end{solution}

\begin{remark}
  $p=8n+5$且
  $a^{2n+1} \equiv - 1 \left(\mod  p\right)$时，要如练习~\ref{求a的平方根}(2) 中
  凑出$a$的一个平方根，我们需要取$-1$的平方根。如果容易观察到一个那自然好了，如本题(2)中。
  否则，可以用$2^{2n+1}$. 
\end{remark}



\begin{exercise}[Kronecker符号]
设非零整数$n$的素分解为$n=up_1^{e_1}\cdots p_k^{e_k}$, 其中$u=\pm1$, $p_i$为互异的素数。
令$a$为整数。  Kronecker符号定义为
  \[
    \kronecker{a}{n} = \kronecker{a}{u} \prod_{i=1}^k \kronecker{a}{p_i}^{e_i},
  \]
  其中$\kronecker{a}{1}=1$, $\kronecker{a}{p_i}$就是Legendre符号。
  对奇素数$p_i$, $\kronecker{a}{p_i}$就是Legendre符号。
  还有$p_i=2$的情形。定义
\[
  \kronecker{a}{2}=\begin{cases}
  0 & \text{若$a$为偶数},\\
  1 & \text{若~}a=\pm 1\left( \mod 8 \right), \\
  -1 &\text{若~} a\equiv   \pm 3\left( \mod 8 \right). 
    \end{cases}
  \]
  Kronecker符号是Jacobi符号的推广，因此$\kronecker{a}{1}=1$. 
  $u=-1$时，定义
  \[
\kronecker{a}{-1}=\begin{cases}
  -1 & \text{若~}a<0, \\
  1 &\text{若~}a\geqslant 0.
    \end{cases}
  \]
  最后令
  \[
\kronecker{a}{0}=\begin{cases}
      1 & \text{若~}a=\pm 1, \\
      0 &\text{否则}.
    \end{cases}
  \]
  上述定义把分母只允许是正奇数的Jacobi符号推广到了任意的分子$a$和分母$n$.
证明：
\begin{enumerate}
  \item 若$(a,n)=1$, 则$\kronecker{a}{n}=\pm 1$; 否则，$\kronecker{a}{n}=0$.

  \item     \(\left( \frac{ab}{n}\right)  = \left( \frac{a}{n}\right) \left( \frac{b}{n}\right)\), 除非 \(n =  - 1\), 其中一个 \(a,b\) 为零且另一个为负。

  \item \(\left( \frac{a}{mn}\right)  = \left( \frac{a}{m}\right) \left( \frac{a}{n}\right)\), 除非 \(a =  - 1\), 其中一个 \(m,n\) 为零且另一个具有奇数部分 (定义如下) 与$3$模$4$同余。

  \item 对于 \(n > 0\), 我们有 \(\left( \frac{a}{n}\right)  = \left( \frac{b}{n}\right)\), 只要 
  \(
  a \equiv  b \mod \left\{  \begin{array}{ll} {4n}, & n \equiv  2\left( \mod 4 \right) , \\  n & \text{否则. } \end{array}\right. 
\)
如果此外 \(a,b\) 具有相同的符号，这个对\(n < 0\)也同样成立。

\item 对于 \(a \nequiv 3\left(\mod 4\right), a \neq  0\), 我们有 \(\left( \frac{a}{m}\right)  = \left( \frac{a}{n}\right)\), 只要 \(m \equiv  n \mod\left\{  \begin{array}{ll} 4\left| a\right| , & a \equiv  2 \left( \mod 4 \right), \\  \left| a\right| & \text{否则. } \end{array}\right. \)
\end{enumerate}
\end{exercise}

我们看到Kronecker符号在一定的条件下与Jacobi符号有相同的基本性质。不过不同的是，Kronecker符号不具有与二次剩余相同的关联性。
特别是，对于偶数 \(\left( \frac{a}{n}\right)\), Kronecker符号 \(n\) 的取值可以独立于 \(a\) 是否为模 \(n\) 的二次剩余或非剩余。

\begin{exercise}[Kronecker符号的二次互反律]
  对于任意非零整数 \(n\), 令 \({n}^{\prime }\) 表示其奇数部分: \(n = {2}^{e}{n}^{\prime }\), 其中 \({n}^{\prime }\) 是奇数(对于 \(n = 0\), 我们令 \({0}^{\prime } = 1\) )。
\begin{enumerate}
  \item 证明以下对称版本的二次互反律：对每一对互素的整数$m,n$: 
    \[
    \left( \frac{m}{n}\right) \left( \frac{n}{m}\right)  =  \pm  {\left( -1\right) }^{\frac{{m}^{\prime } - 1}{2}\frac{{n}^{\prime } - 1}{2}}
  \]
  其中 \(
    \pm =
    \begin{cases}
      +   & \text{如果 \(m \geq  0\) 或 \(n \geq  0\),} \\ 
      - & \text{如果 \(m < 0\) 和 \(n < 0\)}
\end{cases}
\)

\item 证明以下等价的非对称版本的二次互反律：对每一对互素的整数 \(m,n\) 成立: 
  \[
  \left( \frac{m}{n}\right) \left( \frac{n}{\left| m\right| }\right)  = {\left( -1\right) }^{\frac{{m}^{\prime } - 1}{2}\frac{{n}^{\prime } - 1}{2}}\]
\item 对于任意整数 \(n\), 令 \({n}^{ * } = {\left( -1\right) }^{\left( {{n}^{\prime } - 1}\right) /2}n\).
  证明以下的又一个等价的非对称版本：对于每一对整数 \(m,n\) (不必互素) 
  \[
  \left( \frac{{m}^{ * }}{n}\right)  = \left( \frac{n}{\left| m\right| }\right).
\]
\item 
  补充定律也适用于Kronecker符号。这些定律很容易从上述每个版本的二次互反律中得出 (与Legendre符号和Jacobi符号不同，后者需要主定律和补充定律才能完全描述二次互反律)：
  对于任意整数 \(n\), 我们有 \[ \left( \frac{-1}{n}\right)  = {\left( -1\right) }^{\frac{{n}^{\prime } - 1}{2}}; \]
  对于任意奇整数 \(n\), 有 \[
  \left( \frac{2}{n}\right)  = {\left( -1\right) }^{\frac{{n}^{2} - 1}{8}}. \]
\end{enumerate}
\end{exercise}


\section{二次互反律证明}




\begin{exercise}
判断 $x^{2} \equiv-1457 \left(\mod 2389\right)$ 是否有解。
\end{exercise}

\begin{solution}
 应用Jacobi符号的性质我们有
\begin{align*}
  \kronecker{-1457}{2389} &= 
  \kronecker{932}{2389} = \kronecker{2^2}{2389} \kronecker{233}{2389} = 
  \kronecker{2389}{233} = \kronecker{59}{233} = \kronecker{233}{59} \\
  &= \kronecker{56}{59} = \kronecker{2^3}{59}\kronecker{7}{59} = \kronecker{2}{59} \kronecker{7}{59} 
  = \kronecker{59}{7} = \kronecker{3}{7} = -\kronecker{7}{3} = -\kronecker{1}{3} \\
  &= -1.
\end{align*}
故$-1457\left( \mod 2389 \right)$为二次非剩余，$x^{2} \equiv-1457 \left(\mod 2389\right)$ 无解。
\end{solution}

\begin{exercise}
求： $(3 / 73),(19 / 73),(195 / 1901),(365 / 1847)$.
\end{exercise}

\begin{solution}
  我们应用Jacobi符号的性质。特别地，定理3表明：
  若$a, b$为正奇数，\\
  (i) $\kronecker{a}{b}=\kronecker{b}{a}$当且仅当$a$或$b$形如$4k+1$;\\
  (ii) $\kronecker{-1}{b}=1$当且仅当$b$形如$4k+1$;\\
  (iii) $\kronecker{2}{b}=1$当且仅当$b$形如$8k\pm 1$.
  \begin{enumerate}
    \item 由\S4.2例1知$3$为模$p$二次剩余当且仅当$p\equiv \pm 1\left( \mod 12 \right)$. 由于$73\equiv 1\left( \mod 12 \right)$, $(3 / 73)=1$.
    \item 我们有
      \[
        \kronecker{19}{73}= \kronecker{73}{19} = \kronecker{16}{19}=1.
      \]
    \item 我们有
      \[
        \begin{aligned}
          \kronecker{195}{1901} = \kronecker{1901}{195} = \kronecker{146}{195} = 
          \kronecker{2}{195}\kronecker{73}{195} = -\kronecker{195}{73} 
          = -\kronecker{49}{73}
          =-1.
        \end{aligned}
      \]
    \item 我们有
        \begin{align*}
          \kronecker{365}{1847}= 
          \kronecker{1847}{365} = \kronecker{22}{365} = \kronecker{2}{365} \kronecker{11}{365} = -\kronecker{365}{11} 
          = -\kronecker{2}{11} =1.
\tag*{\qedhere}
        \end{align*}
  \end{enumerate}
\end{solution}

\begin{exercise}
求使 $(6 / p)=1$ 的所有奇素数 $p$.
\end{exercise}

\begin{solution}
  见\S4.2练习~\ref{6是模p的二次剩余的条件}.
\end{solution}

\begin{exercise}[二次互反律的Euler形式]
  应用Gauss引理证明二次互反律的Euler形式：
  若$p,q $为奇素数，$a$为不被$p$整除的正整数，$p\equiv \pm q\left( \mod 4a \right)$,
  则$\kronecker{a}{p}=\kronecker{a}{q}$.
\end{exercise}
此版本的二次互反律说明，Legendre符号$\kronecker{a}{p}$的值只依赖于$p$的模$4a$剩余类，
且对满足$p\equiv \pm r\left( \mod 4a \right)$的所有奇素数$p$取值都相同。
在练习~\ref{二次互反律的Euler形式与经典形式的等价性}~中我们将看到此形式与课本中的形式的等价性。

\begin{solution}
  
\end{solution}

\begin{exercise}
  设 $p$ 为奇素数， $4a< p\nmid a$, 证明：$\kronecker{a}{p}=\kronecker{a}{p-4 a}$; 
  特别地，取$a=2$得$\kronecker{2}{p}=\kronecker{2}{p-8}$.
\end{exercise}

\begin{solution}
  我们有
  \[\tag*{\qedhere}
    \kronecker{a}{p}=(-1)^{\frac{p-1}{2}}\kronecker{p-4a}{p} =
    (-1)^{\frac{p-1}{2}} (-1)^{\frac{p-4a-1}{2}\frac{p-1}{2}} \kronecker{p}{p-4a} = 
    \kronecker{p}{p-4a}.
  \]
\end{solution}

\begin{exercise}\label{二次互反律的Euler形式与经典形式的等价性}
  证明二次互反律的Euler形式 (II) 与课本中二次互反律的如下形式 (I) 的等价性：
  对奇素数$p,q$, $\kronecker{q}{p}\kronecker{p}{q}= (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$.
\end{exercise}

\begin{solution}
  先假设二次互反律的Euler形式 (II) 成立，我们来证明形式(I)成立。
  奇素数$p,q$模$4$同余于$\pm 1$. 
  分$p\equiv q\left( \mod 4 \right)$和$p\nequiv q\left( \mod 4 \right)$讨论。
  若$p\equiv q\left( \mod 4 \right)$, 不妨设$p>q$, 这样可令$p=q+4a$ ($a>0$), 则
  \[
  \begin{aligned}
      \kronecker{p}{q} = \kronecker{4a}{q}=\kronecker{a}{q},\quad
        \kronecker{q}{p} = \kronecker{-4a}{p}=\kronecker{-1}{p}\kronecker{a}{p}=(-1)^{\frac{p-1}{2}} \kronecker{a}{p}.
      \end{aligned}
\]
  由Euler形式知$\kronecker{a}{q}=\kronecker{a}{p}$, 因此
  \[
    \kronecker{p}{q}\kronecker{q}{p}=(-1)^{\frac{p-1}{2}}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.
  \]
  故$\kronecker{p}{q}, \kronecker{q}{p}$同号相当于$p,q$模$4$都为$1$.
  若$p\nequiv q\left( \mod 4 \right)$, 则$p\equiv 1\left( \mod 4 \right), q\equiv -1\left( \mod 4 \right)$
  或$p\equiv -1\left( \mod 4 \right), q\equiv 1\left( \mod 4 \right)$. 从而$4\mid p+q$, 
  $p+q= 4a$, 对某个$a>0$.
  此时，
  \[
  \begin{aligned}
      \kronecker{p}{q} =  \kronecker{4a}{q}=\kronecker{a}{q},\quad
      \kronecker{q}{p} = \kronecker{4a}{p}=\kronecker{a}{p}.
      \end{aligned}
\]
  由Euler形式知$\kronecker{a}{q}=\kronecker{a}{p}$, 因此
  \(
    \kronecker{p}{q}=\kronecker{q}{p}.
  \)
  从而
  \[
    \kronecker{q}{p}\kronecker{p}{q}=1= (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}.
  \]
  综上可知，总有形式(I)成立。

  反过来，设形式(I)成立。分$p\equiv q\left( \mod 4 \right)$和$p\nequiv q\left( \mod 4 \right)$讨论。
  若$p\equiv q\left( \mod 4 \right)$, 不妨设$p>q$, 这样可令$p-q= 4p_1\cdots p_s$, 其中$p_i$为素数。
  此时$p\equiv q\left( \mod 4a \right)$, $a$为某些$p_i$的乘积；
  $p\equiv q\left( \mod p_i \right)$.
  要证明$\kronecker{a}{p}=\kronecker{a}{q}$, 只用证明$\kronecker{p_i}{p}=\kronecker{p_i}{q}$.
  若$p_i=2$, 则$p\equiv q\left( \mod 8 \right)$, 由\S4.1系4知$\kronecker{p_i}{p}=\kronecker{p_i}{q}$.
若$p_i$为奇素数，则
\[
  \kronecker{p_i}{p}=(-1)^{\frac{p_i-1}{2}\frac{p-1}{2}} \kronecker{p}{p_i}= 
  (-1)^{\frac{p_i-1}{2}\frac{q-1}{2}} \kronecker{q}{p_i}=\kronecker{p_i}{q}.
\]
$p\equiv q\left( \mod 4 \right)$的情形证毕。
若$p\nequiv q\left( \mod 4a \right)$, 则$p+q=4p_1\cdots p_s$, 其中$p_i$为素数。
不妨设$p\equiv 1\left( \mod 4 \right), q\equiv -1\left( \mod 4 \right)$.
$p\equiv -q\left( \mod 4 \right)$和$p\equiv \pm q\left( \mod 4a \right)$表明
$p\equiv -q\left( \mod 4a \right)$.
要证明$\kronecker{a}{p}=\kronecker{a}{q}$, 只用证明$\kronecker{p_i}{p}=\kronecker{p_i}{q}$.
若有$p_i=2$ ($1\leqslant i\leqslant t$), 则$p\equiv -q\left( \mod 8 \right)$, 
由\S4.1系4知$\kronecker{2}{p}=\kronecker{2}{q}$.
若$p_i$为奇素数，则
\[
  \kronecker{p_i}{p}=\kronecker{p}{p_i}= \kronecker{-q}{p_i}= (-1)^{\frac{p_i-1}{2}}\kronecker{q}{p_i}= 
  \kronecker{p_i}{q}.
\]
 $p\nequiv q\left( \mod 4 \right)$的情形证毕。
  总之，形式(II)成立。
\end{solution}

\section{解二次同余式}



\begin{exercise}
设 $(2 a, m)=1$. 证明： $a x^{2}+b x+c \equiv 0 \left(\mod m\right)$ 有解当且仅当 $x^{2} \equiv \delta \left(\mod m\right)$ 有解 (其中 $\left.\delta=b^{2}-4 a c\right)$, 且前者的解均可由后者的解推导出。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
求解各同余式： $x^{2} \equiv 7 \left(\mod 43\right), x^{2} \equiv 11 \left(\mod 43\right), x^{2} \equiv 15 \left(\mod 163\right)$.
\end{exercise}

\begin{solution}
  见\S4.1, 练习~\ref{求a的平方根(1)举例}.
\end{solution}

\begin{exercise}
求解各同余式： $x^{2} \equiv 7 \left(\mod 37\right), x^{2} \equiv 13 \left(\mod 101\right)$.
\end{exercise}

\begin{solution}
  见\S4.1, 练习~\ref{求a的平方根(2)举例}.
\end{solution}


\begin{exercise}
求解各同余式： $x^{2} \equiv 31 \left(\mod 41\right), x^{2} \equiv 67 \left(\mod 193\right)$.
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
\starmark
证明：模 $p^{2}$ 的二次剩余 $a$ 恰有 $\frac{p(p-1)}{2}$ 个， 恰为 $x^{\frac{p(p-1)}{2}} \equiv 1\left(\mod p^{2}\right)$ 的解 (这里 $p$为奇素数， $(a, p)=1$). 即 $y^{2} \equiv a\left(\mod p^{2}\right)\left(\text{对某~} y\right ) \Leftrightarrow a^{\frac{p(p-1)}{2}} \equiv 1\left(\mod p^{2}\right)$.
\end{exercise}


\begin{solution}

\end{solution}

\begin{exercise}
检测一个整数是否素数， 在理论和应用中很重要。 Fermat 小定理为此提供了必要 (而非充分) 的条件， 称为 Fermat 素性检测： 若 $p$ 为素数， 则必须 $x^{p} \equiv x \left(\mod p\right)$ 对任意整数 $x$成立 $(1<x<p)$. 故逐个取 $x=2,3, \cdots, p-1$, 检测 $x^{p} \equiv x \left(\mod p\right)$.


如果整数 $n$ 通过了 Fermat 素性检测的第一步， 即 $2^{n} \equiv 2 \left(\mod n\right)$, 而 $n$ 又不是素数， 则称 $n$ 是 (2-Fermat) 伪素数 (2-Fermat pseudoprime). 最小的伪素数为 $341=11 \cdot 31$. 实际计算表明， 伪素数并不多 (即通过第一步检测的大多真是素数).

试证明： 伪素数有无限多。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
若整数 $n$ 通过了 Fermat 素性检测的所有必要步骤， 即 $x^{n}=x \left(\mod n\right)$ 对任意整数 $x$ (与 $n$ 互素) 均成立， 而 $n$ 又不是素数， 则称 $n$ 为 Carmichael (卡迈克尔) 数 (Carmichael number, 或 absolute Fermat pseudoprime). 最小的 Carmichael 数是 $561=3 \cdot 11 \cdot 17$, 在 1910 年发现). Carmichael 数的存在实证了： Fermat 素性检测不是完全可靠的 (不充分的). 但 Carmichael数是很少的， 小于 $10^{21}$ 的只有 20138200 个。


试证明 Korselt 定理 (1899)：正合数 $n$ 为Carmichael 数当且仅当 $n$ 无平方因子， 且
\[
(p-1) \mid(n-1) \text { (对任意素数~} p \mid n).
\]
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}[Fermat 逆定理]
证明：若 $a^{n-1} \equiv 1 \left(\mod n\right)$, 且
对任意满足 $n-1> k \mid(n-1)$的$k$有
\(
a^{k} \nequiv 1 \left(\mod n\right),
\)
则 $n=p$ 为素数。
\end{exercise}

\begin{solution}
  由题设可知$(a,n)=1$且$\ord_n a=n-1$. 故$U_n$为$n-1$阶循环群。
  特别地，$\varphi(n)=n-1$.
可知$n$必为素数。
\end{solution}

\begin{exercise}
设 $n=h p^{b}+1$ ($b=1,2$), $h<p$, $p$ 为奇素数， 且 $2^{n-1} \equiv 1,2^{h} \neq 1 \left(\mod n\right)$, 证明： $n$ 为素数。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
设 $n=2^{m} h+1$ 不是模 $p$ 二次剩余 (对某奇素数 $p$ ), $m \geqslant 2, h<2^{m}$. 证明： $n$ 为素数当且仅当 $p^{(n-1) / 2}=-1 \left(\mod n\right)$.
\end{exercise}

\begin{solution}

\end{solution}


